﻿#pragma once
#include "Index.h"

class ISearchRangeInOrderedArr
{
public:
	/**
	 * 在排序数据中查找元素的第一个和最后一个位置.
	 * 数组 二分查找
	 * https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/
	 *
	 * 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。
	 * 请你找出给定目标值在数组中的开始位置和结束位置。
	 * 如果数组中不存在目标值 target，返回 [-1, -1]。
	 * 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
	 */
	virtual std::vector<int> searchRange(std::vector<int>& nums, int target) = 0;
};

class SearchRangeInOrderedArr
{
public:
	class Binary:public ISearchRangeInOrderedArr
	{
	public:
		std::vector<int> searchRange(std::vector<int>& nums, int target) override
		{
			bool hasRange = true;

			const int lower = lowerBound(nums, target);
			if (hasRange && (lower < 0 || nums[lower] != target))
				hasRange = false;

			const int upper = upperBound(nums, target);
			if (hasRange && (upper < 0 || nums[upper] != target))
				hasRange = false;

			if (!hasRange)
				return { -1, -1 };
			else
				return { lower, upper };
		}
	private:
		//返回在nums中第一个大于等于target的数的位置，不存在返回-1
		int lowerBound(std::vector<int>& nums, int target)
		{
			if (nums.empty())
				return -1;
			const int numsSize = nums.size();
			int left = 0, right = numsSize - 1;

			int resultIndex = -1;
			while (left <= right)
			{
				const int mid = (left + right) >> 1;
				if (nums[mid] >= target)
				{
					resultIndex = mid;
					right = mid - 1;
				}
				else // nums[mid]<target
				{
					left = mid + 1;
				}
			}
			return resultIndex;
		}
		//返回在nums中第一个小于等于target的数的位置，不存在返回-1
		int upperBound(std::vector<int>& nums, int target)
		{
			if (nums.empty())
				return -1;
			const int numsSize = nums.size();
			int left = 0, right = numsSize - 1;

			int resultIndex = -1;
			while (left <= right)
			{
				const int mid = (left + right) >> 1;
				if (nums[mid] <= target)
				{
					resultIndex = mid;
					left = mid + 1;
				}
				else //nums[mid]>target
				{
					right = mid - 1;
				}
			}
			return resultIndex;
		}
	};
};


#ifdef DEV_TEST
#include <gtest/gtest.h>
class SearchRangeInOrderedArrTest :public SolutionTestor<ISearchRangeInOrderedArr>
{
protected:
	void LoadSolutions(std::vector<ISearchRangeInOrderedArr*>& solutions) override
	{
		solutions = {
			new SearchRangeInOrderedArr::Binary
		};
	}

	std::unordered_map<int, std::pair<int, int>> statisticNumsRange(const std::vector<int>& nums)
	{
		std::unordered_map<int, std::pair<int, int>> numsRangeMap;

		numsRangeMap[nums.front()].first = 0;
		int lastNum = nums.front();

		for (int i = 1; i < nums.size(); ++i)
		{
			if (nums[i] != lastNum)
			{
				numsRangeMap[lastNum].second = i - 1;

				numsRangeMap[nums[i]].first = i;
				lastNum = nums[i];
			}
		}
		numsRangeMap[lastNum].second = nums.size() - 1;

		return numsRangeMap;
	}
};
TEST_F(SearchRangeInOrderedArrTest, searchRange)
{
	TestForSolutions([this](ISearchRangeInOrderedArr* solution)
		{
			std::vector<int> nums = TestingUtil::randRangeInts(5000, 0, 100);
			//输入的数组非递减
			std::sort(nums.begin(), nums.end());

			//统计在数据中每个数的位置范围
			std::unordered_map<int, std::pair<int, int>> numsRangeMap = statisticNumsRange(nums);

			//需要检查范围的测试数字
			std::vector<int> testNums;
			TestingUtil::randRangeInts(100, -500, 500);
			for (auto& kvp : numsRangeMap)
				testNums.push_back(kvp.first);

			const std::string noResult = "[-1,-1]";
			for (auto& num : testNums)
			{
				auto resultRangeArr = solution->searchRange(nums, num);
				const auto resultRange = FormatedUtil::dumpFormated(resultRangeArr);

				if (!numsRangeMap.count(num))
					ASSERT_EQ(resultRange, noResult);
				else
				{
					std::vector<int> expectResultArr = { numsRangeMap[num].first,numsRangeMap[num].second };
					const auto expectResult = FormatedUtil::dumpFormated(expectResultArr);
					ASSERT_EQ(resultRange, expectResult);
				}
			}
		});
}
#endif
